

import java.util.*;


public class MinTree {
    //kruskal
    static ArrayList<Road> kruskal(G graph, HashMap<String, Road> roadHashMap) {
        ArrayList<Road> res = new ArrayList<>();
        ArrayList<E> edges = graph.es;  //Edge set of storage graph
        ArrayList<E> forest = new ArrayList<E>();  //Store the edge that meets the results
        double all = 0;
        for (E e : edges) {   //Traverse the edge set. When initializing the graph, the edges are sorted by weight
            ArrayList<E> testForest = refreshForest(forest);
            getEnd(testForest, e.v1, e.v2);
            if (endV) {  //Judge whether a loop is formed
                Road road = roadHashMap.get(e.v1.name + e.v2.name);
                res.add(road);
                all = all + road.distance;
                forest.add(e);
            }
        }
        System.out.println("Total mileage" + all);    //Output the edge that meets the condition (no loop, minimum weight)
        return res;
    }

    //The edge set of graph is sorted by weight
    static ArrayList<E> sortEdgeByWeight(ArrayList<E> es) {
        for (int i = 0; i < es.size(); i++) {
            for (int j = 0; j < es.size(); j++) {
                if (es.get(i).Weight < es.get(j).Weight) {
                    Collections.swap(es, i, j);
                }
            }
        }
        return es;
    }
    static boolean endV = true;

    //Judge whether the new edge will form a ring with the existing forest: get the end node of the target point,
    // and judge whether they are the same, if they are the same, there will be a ring
    static void getEnd(ArrayList<E> testForest, V start, V end) {
        for (E e : testForest) {
            if (e.isvisited == false) {
                if (e.v1.equals(start)) {
                    e.isvisited = true;
                    if (e.v2.equals(end)) {
                        endV = false;
                    } else {
                        getEnd(testForest, e.v2, end);
                    }
                } else if (e.v2.equals(start)) {
                    e.isvisited = true;
                    if (e.v1.equals(end)) {
                        endV = false;
                    } else {
                        getEnd(testForest, e.v1, end);
                    }
                }
            }
        }
    }

    //Refresh forest: mark all edges in the forest as not viewed, and initialize the endv flag
    static ArrayList<E> refreshForest(ArrayList<E> forest) {
        endV = true;
        for (E e : forest) {
            e.isvisited = false;
        }
        return forest;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        V a = new V("a");
        V b = new V("b");
        V c = new V("c");
        V d = new V("d");
        V e = new V("e");
        V f = new V("f");
        V g = new V("g");
        V h = new V("h");
        V i = new V("i");
        E e0 = new E(a, b, 4);
        E e1 = new E(a, h, 8);
        E e2 = new E(b, h, 11);
        E e3 = new E(b, c, 8);
        E e4 = new E(h, i, 7);
        E e5 = new E(h, g, 1);
        E e6 = new E(i, c, 2);
        E e7 = new E(i, g, 6);
        E e8 = new E(c, d, 7);
        E e9 = new E(c, f, 4);
        E e10 = new E(g, f, 2);
        E e11 = new E(d, f, 14);
        E e12 = new E(d, e, 9);
        E e13 = new E(f, e, 10);
        G graph = new G();
        graph.addV(a);
        graph.addV(b);
        graph.addV(c);
        graph.addV(d);
        graph.addV(e);
        graph.addV(f);
        graph.addV(g);
        graph.addV(h);
        graph.addV(i);
        ArrayList<E> es = new ArrayList<E>();
        es.add(e0);
        es.add(e1);
        es.add(e2);
        es.add(e3);
        es.add(e4);
        es.add(e5);
        es.add(e6);
        es.add(e7);
        es.add(e8);
        es.add(e9);
        es.add(e10);
        es.add(e11);
        es.add(e12);
        es.add(e13);
        graph.es = sortEdgeByWeight(es);
        // kruskal(graph);
    }

    public static ArrayList<Road> kruskals() {
        PriorityQueue<Road> roadPool = new PriorityQueue<Road>(Graph.allRoads.size(), new Comparator<Road>() {
            @Override
            public int compare(Road r1, Road r2) {
                if (r1.distance < r2.distance) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });
        for (Road road : Graph.allRoads) {
            roadPool.add(road);
        }
        HashMap<String, HashSet<String>> intersectImage = new HashMap<>();
        for (Map.Entry<String, Intersection> entry : Graph.allIntersectionMap.entrySet()) {
            HashSet<String> intersections = new HashSet<>();
            intersections.add(entry.getKey());
            intersectImage.put(entry.getKey(), intersections);
        }

        ArrayList<Road> res = new ArrayList<>();
        double allDis = 0;
        System.out.println("the minTree is ");
        while (roadPool.size() > 0) {
            Road currentRoad = roadPool.remove();
            HashSet<String> pre = intersectImage.get(currentRoad.intersect1);
            HashSet<String> next = intersectImage.get(currentRoad.intersect2);
            if (!pre.equals(next)) {
                res.add(currentRoad);
                System.out.println(currentRoad.intersect1 + "==>" + currentRoad.intersect2 + "(" + currentRoad.roadId + ")");
                allDis = allDis + currentRoad.distance;
                pre.addAll(next);
                for (String intersectionID : pre) {
                    intersectImage.put(intersectionID, pre);//update intersectionSets
                }
            }
        }
        System.out.println("the minTree distance is " + allDis);
        return res;
    }


}
